package com.hsc.box;

/**
 * 创建一个类模拟LinkedList的实现原理：
 * 可扩展性（面向对象思想）思考：代码的可扩展性，健壮性
 * 实现类中继承了一个抽象类，并且实现了接口中定义的主要方法，做了一个良好的规范
 */
public class LinkedBox<T> extends AbstractBox<T> {
    //记录链表首节对象
    private Node<T> first;
    //记录链表尾节点对象
    private Node<T> last;
    //记录有效元素个数
    private int size;

    /**
     * 添加一个元素到链表中
     *
     * @param element
     * @return
     */
    public boolean add(T element) {
        //将element存入一个新的Node对象中，添加至链表的尾端
        this.linkLast(element);
        return true;
    }

    /**
     * 设计一个方法，将指定的元素，添加到指定的位置
     *
     * @param index
     * @param element
     * @return
     */
    public boolean add(int index, T element) {
        return true;
    }


    /**
     * 将元素添加在新的node对象中，并且添加至链表的尾端
     *
     * @param element
     */
    private void linkLast(T element) {
        //获取当前链表的尾节点对象
        //创建一个局部变量
        Node<T> l = last;
        //创建一个新的node对象，将数据包装起来
        //新添加的Node节点对象，记录着上一个节点，也就是当前链表的尾节点，就是当前节点的前节点，因为当前的尾节点是往链表的尾部添加，所以下一个节点是为空的
        Node<T> newNode = new Node(l, element, null);
        //从链表的整个结构去看，将添加的元素节点设置为链表的尾节点
        last = newNode;
        //上面保证了新创建的Node节点跟上下节点建立联系关系
        //需要判断当前的node是否是当前链表的第一个元素
        if (l == null) {
            //如果当前链表的尾节点是null的，说明当前链表是空的，我们添加的元素是链表的第一个元素
            //将当前链表的整体结构进行设置
            //当前的节点是头节点
            first = newNode;
        } else {
            //如果当前的链表的尾节点不是null的，说明链表是存在元素的
            // 需要做两个操作：
            // 1、将当前的节点与前节点进行关联（在上面已经做了）new Node(l, element, null); 2、将前节点跟当前节点进行关联，也就是前节点设置后节点的关联
            l.next = newNode;
        }
        //添加完节点后 链表中的元素+1
        size++;
    }

    /**
     * 根据索引获取对应的元素
     *
     * @param index
     * @return
     */
    public T get(int index) {
        this.rangeCheck(index);
        //调用查找元素的方法
        Node<T> targetNode = this.node(index);
        return targetNode.item;
    }

    /**
     * 根据下标查询的方法
     *
     * @param index
     * @return
     */
    private Node<T> node(int index) {
        //声明一个局部变量获取要寻找的目标元素
        Node<T> targetNode;
        //因为这用的是数据结构的类型的，并不是数组，无法通过下标直接获取到元素
        //判断index的所处的位置范围
        if (index < size >> 1) { //从前往后栈
            //size 右移动一位相当于 size /2,这样执行效率更快
            //如果小于，说明当前的索引的位置处于链表的前半部分，遍历获取到index位置的节点信息
            //获取到当前链表的头节点
            targetNode = first;
            //循环获取，引用传递
            for (int i = 0; i < index; i++) {
                targetNode = targetNode.next;
            }
        } else { //从后往前找
            targetNode = last;
            for (int i = size - 1; i > index; i--) {
                targetNode = targetNode.prev;
            }
        }
        return targetNode;
    }

    /**
     * 设计一个方法，根据索引下标，删除元素
     *
     * @return
     */
    public T remove(int index) {
        //判断当前的索引是否合法
        this.rangeCheck(index);
        //根据index获取到对应元素
        Node<T> targetNode = this.node(index);
        T oldValue = unlink(targetNode);
        return oldValue;
    }

    /**
     * 删除元素的思路，有三种情况：
     * 这里的删除不是将数组的元素直接覆盖，这里是将要删除的节点，前后引用关系全部断掉，也就是链表链接的线给断掉
     * 1、当前元素的是当前的链表的首节点
     * 如果当前是元素是首节点，设置下一个节点为链表的头节点
     * 2、当前元素是尾节点
     * 3、当前的元素是出于中间的节点
     *
     * @param targetNode 需要删除的元素
     * @return
     */
    private T unlink(Node<T> targetNode) {
        //获取当前targetNode节点中的item数据
        T oldValue = targetNode.item;
        //获取当前元素节点记录的上一个节点元素
        Node<T> prevNode = targetNode.prev;
        //获取当前元素节点记录的的下一个节点元素
        Node<T> nextNode = targetNode.next;
        //如果当前元素的前节点为空，说明当前的元素节点是链表的头节点,当前的node是第一个
        if (prevNode == null) {
            //将当前元素节点的下节点设置为当前链表的头节点
            first = nextNode;
        } else {
            //如果不为空，说明当前的元素节点不是头节点，可能是中间的节点
            //1、需要将当前的节点前节点跟当前节点的后节点进行指向
            prevNode.next = nextNode;
            //当前的节点的前节点与当前节点的后节点建立连续后，当前节点与前节点联系断开（置空）
            targetNode.prev = null;
        }
        //如果当前的节点后节点为空，说明当前节点是尾节点
        if (nextNode == null) {
            //直接当前节点前节点设置为链表中最后一个节点元素
            last = prevNode;
        } else {
            //如果链表中不是尾节点元素，说明是中间的节点
            //将当前节点的后节点跟当前节点的前节点进行关联
            nextNode.prev = prevNode;
            targetNode.next = null;
        }
        //当前的元素完成对上后节点之间联系，并且当前元素的前后指向也置空，断开链接
        //链表元素减1
        size--;
        return oldValue;
    }

    public int size() {
        return size;
    }

    private void rangeCheck(int index) {
        //判断当前传入的下标是否符合范围内
        if (index < 0 || index > size) {
            //如果当前的下标小于0或者大于当前的数组的存储的元素数量，直接抛出异常，告诉不合理的范围数组下标
            //自己定义一个异常(自己创建的类)来说明这个问题
            new BoxIndexOutOfBoundsException("Index:" + index + ",Size:" + size);
        }
    }


    //内部类，将一个类，放在另一类的内部
    //Node是linkedBox的全局内部类
    //只有当的linkedBox类使用，别人用不到
    //隐藏了底层的机制

    /**
     * 创建一个对象用来存储元素，在链表的数据结构中：由一个个的节点链接而成
     * 一个节点包含中包含着三个部分组成的元素：下一个元素的引用地址信息，当前节点的具体数据，上一个节点的地址引用
     */
    private static class Node<T> {
        //上一个节点的对象
        Node prev;
        //当前的节点的数据
        T item;
        //下一个节点对象
        Node next;

        //提供一个封装数据的构造方法
        public Node(Node prev, T item, Node next) {
            this.prev = prev;
            this.item = item;
            this.next = next;
        }
    }


}
